package UnitTest;

import java.util.stream.IntStream;

/**
 * @Auther: Administrator
 * @Date: 2019/9/5/005 20 01
 * @Description: 分布式计算
 * 在m个节点的分布式计算系统中，有一批任务需要执行，每个任务需要执行的时间arrays[i],
 * 每个节点同一时间只能执行一个任务，每个节点只能执行连续的任务，例如i，i+1,i+2,但
 * 是不能执行i,i+2，请问任务完成的最短时间
 */
public class DistributedCal {
    public static void main(String[] args) {
        int[] nums = {7,2,5,10,8,};int m = 2;
        Integer max = solution(m, nums);
        System.out.println(max);
    }
    /**
     * @param m    节点
     * @param nums 任务需要的时间数组
     */
    public static Integer solution(int m, int[] nums) {
        //节点数m>n时,max即为最短时间
        int max = IntStream.of(nums).max().getAsInt();
        //节点数m=1s时,sum即为最短时间 由题意得,m增大，mintime 变化范围 max->sum
        int sum = IntStream.of(nums).sum();
        int lo = max;
        int hi = sum;
        while (lo < hi) {
            int middle = lo + (hi - lo)/2 ;
            int pieces = split(middle, nums);
            if (pieces > m) {
                lo = middle + 1;
            } else {
                hi = middle;
            }
        }
        return lo;
    }
    private static int split(int middle, int[] nums) {
        int sum = 0;
        int count = 1;
        for (int num : nums) {
            if (sum + num > middle) {
                sum = num;
                count++;
            } else {
                sum += num;
            }
        }
        return count;
    }
}
